#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <limits.h>
#include "graph.h"

using namespace std;

/* --------------------------------- *
 * PAIR CLASS                        *
 * --------------------------------- */

/* Construtor */
Pair::Pair(int n, int w): node(n), weight(w) { };

/* Sobrecarga do operado << para impressao */
ostream& operator<< (ostream &out, Pair &p)
{
  cout << "[Node: " << p.node << ", Weight: " << p.weight << "]";
  return out;
}

/* Sobrecarga do opeador ==, que eh usada na remocao */
int Pair::operator== (const Pair &p) const
{
  if(this->node == p.node)
    return true;
  else
    return false;
}

/* --------------------------------- *
 * GRAPH CLASS                       *
 * --------------------------------- */

/*Construtuor da classe Graph*/
Graph::Graph(){
  numEdges = 0;
  numNodes = 0;
}

/* Adiciona node2 a lista de adjacencia do node1 com um certo peso weight e o 
   contrario tambem, uma vez que o grafo nao e direcionado */
void Graph::add(int node1, int node2, int weight)
{
  Pair p1(node1, weight);
  Pair p2(node2, weight);

  if (pairMap[node1].size() == 0)
      numNodes++;
  if (pairMap[node2].size() == 0)
      numNodes++;

  pairMap[node1].push_back(p2);
  pairMap[node2].push_back(p1);
  numEdges++;
}

/* Remove a aresta que liga os nodos */
void Graph::remove(int node1,int node2)
{
  list<Pair>::iterator it_l;
  
  if (pairMap[node1].size() == 1)
    numNodes--;
  if (pairMap[node2].size() == 1)
    numNodes--;

  for(it_l=pairMap[node1].begin(); it_l !=pairMap[node1].end(); it_l++)
  {
    if((*it_l).node == node2)
    {
      pairMap[node1].erase(it_l);
      break;
    }
  }
  for(it_l=pairMap[node2].begin(); it_l !=pairMap[node2].end(); it_l++)
  {
    if((*it_l).node == node1)
    {
      pairMap[node1].erase(it_l);
      break;
    }
  }
  numEdges--;
}

/* Retorna o numero de nodos em um grafo */
int Graph::getNumNodes()
{
  return numNodes;
}

/* Retorna o custo entre dois nodos ou infinito caso não haja aresta e edgeCost(i,i) = 0  */
int Graph::edgeCost(int node1, int node2)
{
  if(node1==node2) return 0;

  list<Pair>::iterator i;
  for(i=pairMap[node1].begin(); i!=pairMap[node1].end(); i++)
    if((*i).node == node2) return (*i).weight;
  
  return INT_MAX;
}

/* Verifica se todos os nodos do grafo contem numero par de arestas */
bool Graph::isEulerian()
{
  map<int, list<Pair> >::iterator it_m;

  for(it_m = pairMap.begin(); it_m != pairMap.end(); it_m++)
  {
    if( (*it_m).second.size() % 2 != 0 )
    {
      return false;
    }
  }
  return true;
}

/* Retorna o circuito de um grafo euleriano*/
list<int> Graph::getEulerian()
{
  list<int> C;
  Graph tmp = *(this);
  
  int currentNode;
  list<Pair>::iterator currentEdge;

  currentNode = (*(tmp.pairMap.begin())).first;
  C.push_back(currentNode);

  for(currentEdge = tmp.pairMap[currentNode].begin(); currentEdge != tmp.pairMap[currentNode].end(); currentEdge++)
  {
    if( tmp.pairMap[currentNode].size() == 1 || tmp.isBridge(currentNode,(*currentEdge).node,numNodes) == false )
    {
      tmp.remove(currentNode,(*currentEdge).node);
      currentNode = (*currentEdge).node;
      currentEdge = --(tmp.pairMap[currentNode].begin());
      C.push_back(currentNode);
    }
  }
  
  return C;
}

/* Retorna uma lista com os nodos de grau impar */
list<int> Graph::getOdds()
{

  list<int> odds;

  map<int, list<Pair> >::iterator it_m;
  list<Pair>::iterator it_l;

  for(it_m = pairMap.begin(); it_m != pairMap.end(); it_m++)
  {
    if( (*it_m).second.size() % 2 != 0 )
    {
      odds.push_back((*it_m).first);
    }
  }
  return odds;

}
/* Retorna a menor distancia de todos os vertice abertos */
int getMin(map<int, bool> vertex, map<int, int> distance)
{
  int min=INT_MAX;
  int answer;
  map<int, bool>::iterator i;
  for(i=vertex.begin(); i!=vertex.end(); i++)
  {
    if(min>distance[(*i).first]) 
    {
      min=distance[(*i).first];
      answer=(*i).first;
    }
  }
  return answer;
}

/* Dado um ponto de partida, calcula o menor caminho até todos os vértices do grafo.
 * O resultado sao dois vetores:
 *   - Previous: para encontrar o caminho ate determinado vertice encontre ele no vetor
 *               e siga o caminho retroativamente
 *   - Distance: distancia do vertice inicial ate o vertice no vetor.
 */
void Graph::dijkstra(int source)
{
  map<int, int> distance;
  map<int, int> previous;
  map<int, bool> vertex;
  int min, sum;

  //Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às demais estimativas.
  map<int, list<Pair> >::iterator i;
  list<Pair>::iterator i2;
  for(i=pairMap.begin(); i != pairMap.end(); i++)
  {
    distance[(*i).first]=INT_MAX;
    vertex[(*i).first]=1;
  }
  distance[source]=0;

  //Enquanto houver vertices abertos
  while(!vertex.empty())
  {
    //seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os vértices abertos
    min=getMin(vertex, distance);
    //feche o vértice k
    vertex.erase(min);

    for(i2=pairMap[min].begin(); i2 != pairMap[min].end(); i2++)
    {
      // Para todo vértice j ainda aberto que seja sucessor de k faça: 
      if(vertex.find((*i2).node)!=vertex.end())
      {
        //some a estimativa do vértice k  com o custo do arco que une k  a j; 
        sum=distance[min]+(*i2).weight;
        //caso esta soma seja melhor que a estimativa anterior para o vértice j, substitua-a e anote k como precedente
        //de j.
        if(sum < distance[(*i2).node])
        {
          distance[(*i2).node]=sum;
          previous[(*i2).node]=min;
        }
      }
    }
  }

  //imprime
  map<int, int>::iterator i3;

  cout << endl << "Previous" << endl;
  for(i3=previous.begin(); i3!=previous.end(); i3++)
  {
    cout << (*i3).first << "=>" << (*i3).second << endl;
  }
  cout << endl;
}

/* Floyd Warshall - calcula o menor caminho de todos os vertices para todos os vertices */
void Graph::floydWarshall(int** path, int** next)
{
  int n=numNodes;

  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
      path[i][j]=edgeCost(i, j);
  
  for(int k=0; k<n; k++)
    for(int i=0; i<n; i++)
      for(int j=0; j<n; j++)
      {
        if( path[i][k]!=INT_MAX && path[k][j]!=INT_MAX 
           && path[i][k]+path[k][j] < path[i][j])
        {
          path[i][j] = path[i][k]+path[k][j];
          next[i][j] = k;
        }
      }
}

/* Retorna o caminho de um vertice até outra, após realizar o Floyd Warshall */
list<int> Graph::getPath(int i, int j, int** path, int** next)
{
  list<int> solution;
  list<int> temp;

  if(path[i][j]==INT_MAX)
  {
    return solution;
  }

  int intermediate = next[i][j];
  if(intermediate == -1)
  {
    return solution;
  }
  else
  {
    temp = getPath(i, intermediate, path, next);
    solution.insert(solution.end(),temp.begin(),temp.end());
    
    solution.push_back(intermediate);
    
    temp = getPath(intermediate, j, path, next);
    solution.insert(solution.end(),temp.begin(),temp.end());
  }
  return solution;
}

/* Retorna uma lista com os pares de vertices de menor custo total */
list<int> Graph::getDoubles(int **path,list<int> vetor)
{
  list<int> solucao,temp,temp2,temp3;
  int min,sum,first;

  if(vetor.size() == 2){
    return vetor;
  }

  first = vetor.front();

  list<int>::iterator it_l,it_l2;
  min = INT_MAX;
  for(it_l = ++(vetor.begin()); it_l != vetor.end(); it_l++)
  {

    temp3 = vetor;
    sum=0;
    temp.clear();
    temp.push_back(first);
    temp.push_back((*it_l));
    temp3.remove(first);
    temp3.remove((*it_l));

    temp2 = getDoubles(path,temp3);
    
    temp.insert(temp.end(),temp2.begin(),temp2.end());

    for(it_l2 = temp.begin(); it_l2 != temp.end(); it_l2++)
    {
      sum +=path[(*it_l2)][(*(++it_l2))];
    }

    if ( sum < min ){
      solucao = temp;
      min = sum;
    }
  }

  return solucao;

}

/* Duplica os caminhos entre todas as arestas passadas por parâmetro */
void Graph::duplicateEdges(list<int> pairs,int **path,int **next)
{

  list<int> path_l;
  list<int>::iterator it_l,it_l2;
  int first;

  for(it_l = pairs.begin(); it_l != pairs.end(); it_l++)
  {
    first = (*it_l);

    path_l = getPath(first,(*(++it_l)),path,next);

    
    for(it_l2 = path_l.begin(); it_l2 != path_l.end(); it_l2++)
    {
      (*this).add(first,(*it_l2),edgeCost(first,(*it_l2)));
      cout << "Duplicando aresta " << first << " " << (*it_l2) << endl;
      first = (*it_l2);
    }
    if( path_l.empty() == false)
    {
      cout << "Duplicando aresta " << path_l.back() << " " << (*it_l) << endl;
      (*this).add(path_l.back(),(*it_l),edgeCost(path_l.back(),(*it_l)));
    }
    else{
      cout << "Duplicando aresta " << first << " " << (*it_l) << endl;
      (*this).add(first,(*it_l),edgeCost(first,(*it_l)));
    }
  }

}

/* Retorna se a aresta que liga dois vértices é ponte para um grafo de determinado tamanho */
bool Graph::isBridge(int node1,int node2,int tamanho)
{
  int *visitados = (int*)malloc(sizeof(int)*tamanho);
  for(int i =0;i<tamanho;i++)
    visitados[i] = 0;

  int size = numNodes;

  bool booleano;

  Graph tmp = (*this);

  tmp.remove(node1,node2);

  booleano = tmp.DFS(visitados,(*((*this).pairMap.begin())).first) != size;


  return booleano;
}

/* Busca em profundidade - retorna o número de vértices coloridos */
int Graph::DFS(int *visitados,int inicial)
{
  int solution=1;

  visitados[inicial] = 1;

  map<int, list<Pair> >::iterator it_m;
  list<Pair>::iterator it_l;

  for(it_l = pairMap[inicial].begin(); it_l != pairMap[inicial].end(); it_l++)
  {
    if(visitados[(*it_l).node] == 0)
    {
      solution+=(*this).DFS(visitados,(*it_l).node);
    }
  }

  return solution;
}
/* Sobrecarga do operador << para impressao */
ostream& operator<<(ostream& out, Graph& g)
{
  map<int, list<Pair> >::iterator it_m;
  list<Pair>::iterator it_l;

  cout << "Number of Nodes => " << g.numNodes << endl;
  cout << "Number of Edges => " << g.numEdges << endl;
  //Itera sobre o map de lists
  for(it_m = g.pairMap.begin(); it_m != g.pairMap.end(); it_m++)
  {
    //Imprime o indice do mapa
    cout << (*it_m).first << " =>";
    
    //Itera sobre a lista de pairs
    for(it_l=(*it_m).second.begin(); it_l !=(*it_m).second.end(); it_l++)
    {
      //Imprime o pair
      cout << " " << (*it_l);
    }
    cout << endl;
  }

  return out;
}

int main()
{
  Graph g;
  list<int> impares,pares;
  /* Le a entrada de stdin */
  int edge1;
  int edge2;
  int weight;
  while( scanf("%d %d %d",&edge1,&edge2,&weight) > 0)
    g.add(edge1,edge2,weight);


  cout << "******* Grafo Original ********" << endl << g << endl << endl;
  if( g.isEulerian() == false)
  {

    cout << "O grafo não é euleriano" << endl << endl << endl;
    impares = g.getOdds();    
    int n=g.getNumNodes();
    int** path=(int**)malloc(sizeof(int*)*n);
    int** next=(int**)malloc(sizeof(int*)*n);
    for(int i=0; i<n; i++)
    {
      path[i]=(int*)malloc(sizeof(int)*n);
      next[i]=(int*)malloc(sizeof(int)*n);
    }
    
    for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
    {
      path[i][j]=-1;
      next[i][j]=-1;
    }
    
    g.floydWarshall(path, next);
    pares = Graph::getDoubles(path,impares);

    list<int>::iterator it_l;
    cout << "Caminhos duplicados: ";
    for(it_l = pares.begin(); it_l != pares.end() ; it_l++)
    {
      cout << (*it_l); 
      cout << "&" << (*(++it_l)) << " ";
    }
    cout << endl;

    g.duplicateEdges(pares,path,next);

    cout << endl << endl;

    cout << g;
    
  }
  else
    cout << "O grafo é euleriano" << endl << endl << endl;

  /* Pega o caminho minimo */
  list<int> solution;
  solution = g.getEulerian();
  
  /* Imprime a solucao */
  list<int>::iterator it_l;
 
  cout << "\n\n****** Circuito Euleriano *******" << endl;
  for(it_l = solution.begin(); it_l != --(solution.end()) ; it_l++)
    cout << (*it_l) << " => ";
  cout << (*it_l) << endl;

 }
